package vj.array;

import java.util.Arrays;
import java.util.Random;

/*
 * . For 2 sorted arrays one with size X and another with size X+Y which has
 *  only Y elements. merge these arrays in to second array such that
 *   resultant array at end will be sorted.
 */

public class MergeArrays {

	public static void main(String[] args) {
		int a[] = new int[24];
		Random r = new Random();
		for(int j = 0; j < 20; j++) {
			a[j] = r.nextInt(25) + 1;
		}
		Arrays.sort(a, 0, 20);
		for(int j = 0; j < 20; j++) {
			System.out.print(a[j] + " ");
		}
		
		int b[] = new int[] {5, 16, 16, 67};
		merge(a, b);
		System.out.println();
		for(int j = 0; j < a.length; j++) {
			System.out.print(a[j] + " ");
		}
	}
	
	public static void merge1(int a[], int b[]) {
		int aend = a.length - b.length - 1;
		int astrt = 0; 
		for(int i = 0; i < b.length; i++) {
			while(a[astrt] < b[i]) {
				astrt++;
			}
			slide(a, astrt, aend);
			a[astrt] = b[i];
			aend++;
		}
	}

	private static void slide(int[] a, int astrt, int aend) {
		int prev = a[astrt];
		int temp;
		for(int i = astrt + 1; i <= aend; i++) {
			temp = a[i];
			a[i] = prev;
			prev = temp;
		}
		a[aend + 1] = prev;
	}
	
	public static void merge(int X[], int Y[]) {
		int k = X.length - 1;
		int i = X.length - Y.length - 1;
		for(int j = Y.length - 1; j >= 0; j--) {
			while(X[i] > Y[j]) {
				X[k] = X[i];
				i--;
				k--;
			}
			X[k] = Y[j];
			k--;
		}
	}
	
	
}
